package com.c2b.algorithm.leetcode.jzoffer;

/**
 * <a href="https://leetcode.cn/problems/que-shi-de-shu-zi-lcof/">0～n-1中缺失的数字</a>
 * <p>一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。
 * 在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。</p>
 * <pre>
 * 示例 1:
 *      输入: [0,1,3]
 *      输出: 2
 * 示例 2:
 *      输入: [0,1,2,3,4,5,6,7,9]
 *      输出: 8
 *
 * 限制：1 <= 数组长度 <= 10000
 * </pre>
 *
 * @author c2b
 * @since 2023/4/7 9:37
 */
public class JzOffer0053MissingNumber_II {

    public int missingNumber(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != i) {
                return i;
            }
        }
        return nums.length;
    }

    /**
     * 位运算
     * <p>
     * 数组nums 中有n−1个数，在这 n−1个数的后面添加从 0到n−1 的每个整数，则添加了n个整数，共有2n−1 个整数。<br>
     * 在2n−1 个整数中，缺失的数字只在后面 n个整数中出现一次，其余的数字在前面n−1 个整数中（即数组中）和后面 n个整数中各出现一次，即其余的数字都出现了两次。
     * <p>
     * 根据出现的次数的奇偶性，可以使用按位异或运算得到缺失的数字。按位异或运算⊕ 满足交换律和结合律，且对任意整数x都满足 x⊕x=0 和x⊕0=x。
     * <p>
     * 由于上述 2n−1个整数中，缺失的数字出现了一次，其余的数字都出现了两次，因此对上述2n−1 个整数进行按位异或运算，结果即为缺失的数字。
     *
     * </p>
     */
    public int missingNumber2(int[] nums) {
        int xor = 0;
        for (int i = 0; i < nums.length; i++) {
            xor ^= nums[i];
            xor ^= i;
        }

        xor ^= nums.length;
        return xor;
    }

    public static void main(String[] args) {
        JzOffer0053MissingNumber_II jzOffer0053MissingNumber_ii = new JzOffer0053MissingNumber_II();
        System.out.println(jzOffer0053MissingNumber_ii.missingNumber2(new int[]{0, 1, 3}));
    }
}
